|
In mathematics, the Erdős–Szekeres theorem is a finitary result that makes precise one of the corollaries of Ramsey's theorem. While Ramsey's theorem makes it easy to prove that every sequence of distinct real numbers contains a monotonically increasing infinite subsequence ''or'' a monotonically decreasing infinite subsequence, the result proved by Paul Erdős and George Szekeres goes further. For given ''r'', ''s'' they showed that any sequence of length at least (''r'' − 1)(''s'' − 1) + 1 contains a monotonically increasing subsequence of length ''r'' ''or'' a monotonically decreasing subsequence of length ''s''. The proof appeared in the same 1935 paper that mentions the Happy Ending problem. == Example == For ''r'' = 3 and ''s'' = 2, the formula tells us that any permutation of three numbers has an increasing subsequence of length three or a decreasing subsequence of length two. Among the six permutations of the numbers 1,2,3: * 1,2,3 has an increasing subsequence consisting of all three numbers * 1,3,2 has a decreasing subsequence 3,2 * 2,1,3 has a decreasing subsequence 2,1 * 2,3,1 has two decreasing subsequences, 2,1 and 3,1 * 3,1,2 has two decreasing subsequences, 3,1 and 3,2 * 3,2,1 has three decreasing length-2 subsequences, 3,2, 3,1, and 2,1. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Erdős–Szekeres theorem」の詳細全文を読む スポンサード リンク
|